package demo3;

import java.util.Arrays;

/**
 * 插入排序
 */
public class SimpleInsertSort {
    public static void main(String[] args) {
        int[] arr = new int[]{4,2,9,5,1,16,3};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void insertSort(int[] arr) {

        // 遍历所有数字, 默认第一个已经拍好序了
        for (int i = 1; i < arr.length; i++) {
            // 把当前数字记录下来
            int temp = arr[i];
            int j;
            // 遍历当前数字前面所有数字,找到不比当前数字小的位置停止
            for (j = i-1; j >= 0 && temp < arr[j] ; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }

}
